package cn.com.leetcode.dp;

/**
 * 给定一个整数数组，找出总和最大的连续数列，并返回总和。
 * <p>
 * 示例：
 * <p>
 * 输入： [-2,1,-3,4,-1,2,1,-5,4]
 * 输出： 6
 * 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * 进阶：
 * <p>
 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/contiguous-sequence-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo_Ms16_17 {
    public static void main(String[] args) {
        int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4, -5, 1, 2, 3, 4, 5, -10, 1, 4, 13, -7, -1};
        Demo_Ms16_17 demo_ms16_17 = new Demo_Ms16_17();
        int maxNum = demo_ms16_17.maxSubArray(nums);
        System.out.println(maxNum);
    }

    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            sum += num;

            if (max < sum) {
                max = sum;
            }

            if (sum < 0) {
                sum = 0;
            }


        }
        return max;
    }
}
